package leetcode.weekly.week330;

import leetcode.helper.H;

//Solution4Test
public class Solution41 {

	public long countQuadruplets(int[] nums) {
		int n = nums.length;
		int[][] dp = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n - 1; j++) {
				dp[j + 1][i] = dp[j][i] + (nums[j] < nums[i] ? 1 : 0);
			}
		}
		long ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (nums[i] > nums[j]) {
					ans += dp[i][j] * (n - nums[i] - (j - dp[j][i] - 1));
				}
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution41 so = new Solution41();
		so.countQuadruplets(H.str2array3("[1,3,2,4,5]"));
	}

}
